package LC;

/**
 * https://leetcode.com/problems/intersection-of-two-linked-lists/description/
 * Write a program to find the node at which the intersection of two singly linked lists begins.
 * For example, the following two linked lists:
 * A:          a1 → a2
 * ↘
 * c1 → c2 → c3
 * ↗
 * B:      b1 → b2 → b3
 * begin to intersect at node c1.
 * Notes:
 * If the two linked lists have no intersection at all, return null.
 * The linked lists must retain their original structure after the function returns.
 * You may assume there are no cycles anywhere in the entire linked structure.
 * Your code should preferably run in O(n) time and use only O(1) memory.
 * Credits:
 * Special thanks to @stellari for adding this problem and creating all test cases.
 */
public class LC_160_IntersectionofTwoLinkedLists_LinkedList {
    public static void main(String[] args) {
        ListNode h1 = new ListNode(1);
        h1.next = new ListNode(2);
        ListNode h2 = new ListNode(100);
        h2.next = new ListNode(101);
        h1.next.next = new ListNode(50);
        h2.next.next = h1.next.next;
        ListNode intersectionNode = Solution.getIntersectionNode(h1, h2);
        System.out.println(intersectionNode.val);
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    static class Solution {
        static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            int len1 = 0;
            int len2 = 0;
            ListNode p1 = headA, p2 = headB;
            if (p1 == null || p2 == null)
                return null;
            while (p1 != null) {
                len1++;
                p1 = p1.next;
            }
            while (p2 != null) {
                len2++;
                p2 = p2.next;
            }
            int diff = 0;
            p1 = headA;
            p2 = headB;
            if (len1 > len2) {
                diff = len1 - len2;
                int i = 0;
                while (i < diff) {
                    p1 = p1.next;
                    i++;
                }
            } else {
                diff = len2 - len1;
                int i = 0;
                while (i < diff) {
                    p2 = p2.next;
                    i++;
                }
            }
            while (p1 != null && p2 != null) {
                if (p1.val == p2.val) {
                    return p1;
                }
                p1 = p1.next;
                p2 = p2.next;
            }
            return null;
        }
    }

}